﻿// BM11 链表相加(二)
// https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
//  deque.back(); 空导致卡死

#include <algorithm>
#include <iostream>
#include <memory>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};

ListNode* nodeAdd(ListNode* t1, ListNode* t2) {
  if (t1 && t2) {
    t1->val += t2->val;
    return t1;
  }
  if (t1) return t1;
  return t2;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
  // write code here
  if (head1 == nullptr) {
    return head2;
  }
  if (head2 == nullptr) {
    return head1;
  }
  deque<ListNode*> dqNode1;
  deque<ListNode*> dqNode2;
  ListNode* p = head1;
  while (p) {
    dqNode1.push_back(p);
    p = p->next;
    printf(".p1");
  }
  p = head2;
  while (p) {
    dqNode2.push_back(p);
    p = p->next;
    printf(".p2");
  }
  int carry = 0;
  ListNode* newHead = new ListNode(0);
  ListNode* curHead = newHead->next;  // is null
  while (!dqNode1.empty() || !dqNode2.empty()) {
    ListNode* t1 = dqNode1.back();
    dqNode1.pop_back();
    ListNode* t2 = dqNode2.back();
    dqNode2.pop_back();
    ListNode* t3 = nodeAdd(t1, t2);
    if (t3->val >= 10) {
      t3->val -= 10;
      carry = 1;
    } else {
      carry = 0;
    }
    t3->next = curHead;
    curHead = t3;
    if (t1) printf("t1=%d.", t1->val);
    if (t2) printf("t2=%d.", t2->val);
    if (t3) printf("t3=%d.", t3->val);
    printf("\n");
  }
  if (carry > 0) {
    ListNode* t3 = new ListNode(carry);
    t3->next = curHead;
    curHead = t3;
  }
  return curHead;
}

int main_bm11() {
  deque<int*> dqNumber;
  printf(".. n..");

  int* num1 = dqNumber.back();
  printf(".. ");
  dqNumber.pop_back();
  printf("%p\n", num1);

  int* num2 = dqNumber.back();
  dqNumber.pop_back();
  printf("%p\n", num2);
  int* num3 = dqNumber.back();
  dqNumber.pop_back();
  printf("%p\n", num3);

  printf(".. ");
  int i = 0;
  ListNode* head1[10];
  head1[i++] = new ListNode(1);
  head1[i++] = new ListNode(2);
  head1[i++] = new ListNode(3);
  for (int i = 0; i < 9; i++) {
    head1[i]->next = head1[i + 1];
  }

  i = 0;
  ListNode* head2[10];
  head2[i++] = new ListNode(6);
  head2[i++] = new ListNode(7);
  head2[i++] = new ListNode(8);
  head2[i++] = new ListNode(9);
  for (int i = 0; i < 9; i++) {
    head2[i]->next = head2[i + 1];
  }
  addInList(head1[0], head2[0]);
  printf("end\n");
  return 0;
}
